#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 数据结构定义
typedef struct {
    int id;        // 物品原始编号
    int weight;
    double value;
    double ratio;  // 价值密度
} bItem;

typedef struct {
    int *selected;
    double total_value;
    int total_weight;
    double time_cost;
    int timeout;  // 是否超时
} Result;

// 全局变量（用于回溯法）
double b_max_value = 0;
int b_best_weight = 0;
int *b_best_solution;
int *b_current_solution;
double b_current_value = 0;
int b_current_weight = 0;

// 时间控制
clock_t start_time;
double time_limit = 300.0;  // 时间限制：5分钟

// 检查是否超时
int is_timeout() {
    clock_t current_time = clock();
    double elapsed = ((double)(current_time - start_time)) / CLOCKS_PER_SEC;
    return elapsed > time_limit;
}

// 从文件读取测试数据
bItem* load_test_data(const char* filename, int* n) {
    FILE *file = fopen(filename, "r");
    if (file == NULL) {
        printf("无法打开文件 %s\n", filename);
        return NULL;
    }
    
    // 读取物品数量
    fscanf(file, "%d", n);
    
    // 分配内存并读取物品数据
    bItem *items = malloc(*n * sizeof(bItem));
    
    for (int i = 0; i < *n; i++) {
        items[i].id = i;  // 记录原始编号
        fscanf(file, "%d %lf", &items[i].weight, &items[i].value);
        items[i].ratio = items[i].value / items[i].weight;
    }
    
    fclose(file);
    return items;
}

// 按价值密度降序排序（用于优化界限计算）
void sort_by_ratio(bItem items[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (items[j].ratio < items[j + 1].ratio) {
                bItem temp = items[j];
                items[j] = items[j + 1];
                items[j + 1] = temp;
            }
        }
    }
}

// 计算剩余物品的最大可能价值（用于剪枝）
double bound(int i, int n, bItem *items, double capacity) {
    double remaining_capacity = capacity - b_current_weight;
    double bound_value = b_current_value;
    
    while (i < n && items[i].weight <= remaining_capacity) {
        remaining_capacity -= items[i].weight;
        bound_value += items[i].value;
        i++;
    }
    
    // 如果还有剩余容量和物品，可以取部分物品（分数背包的上界）
    if (i < n && remaining_capacity > 0) {
        bound_value += items[i].value * (remaining_capacity / items[i].weight);
    }
    
    return bound_value;
}

// 回溯函数
int backtrack(int i, int n, bItem *items, double capacity) {
    // 检查超时
    static int call_count = 0;
    call_count++;
    if (call_count % 50000 == 0) {  // 每5万次调用检查一次
        if (is_timeout()) {
            return 1;  // 返回超时标志
        }
        
        // 显示进度信息
        if (call_count % 500000 == 0) {
            printf("    已执行 %d 次递归调用，当前最优值: %.2f\n", call_count, b_max_value);
        }
    }
    
    // 到达叶子节点，更新最优解
    if (i == n) {
        if (b_current_value > b_max_value) {
            b_max_value = b_current_value;
            b_best_weight = b_current_weight;
            for (int j = 0; j < n; j++) {
                b_best_solution[j] = b_current_solution[j];
            }
        }
        return 0;
    }
    
    // 剪枝：如果当前重量加上当前物品的重量不超过背包容量
    if (b_current_weight + items[i].weight <= capacity) {
        // 选择当前物品
        b_current_solution[items[i].id] = 1;
        b_current_weight += items[i].weight;
        b_current_value += items[i].value;
        
        // 回溯
        if (backtrack(i + 1, n, items, capacity)) {
            return 1;  // 传播超时信号
        }
        
        // 恢复状态
        b_current_solution[items[i].id] = 0;
        b_current_weight -= items[i].weight;
        b_current_value -= items[i].value;
    }
    
    // 剪枝：如果剩余物品的最大可能价值大于当前最大价值，才考虑不选当前物品
    if (bound(i + 1, n, items, capacity) > b_max_value) {
        // 不选择当前物品
        b_current_solution[items[i].id] = 0;
        if (backtrack(i + 1, n, items, capacity)) {
            return 1;  // 传播超时信号
        }
    }
    
    return 0;
}

// 回溯法求解0-1背包问题
Result backtrack_knapsack(bItem items[], int n, int capacity) {
    Result result = {0};
    result.selected = calloc(n, sizeof(int));
    result.timeout = 0;
    
    printf("    物品数量: %d，开始处理...\n", n);
    printf("    按价值密度排序物品...\n");
    
    // 按价值密度排序以优化界限计算
    sort_by_ratio(items, n);
    
    // 初始化全局变量
    b_max_value = 0;
    b_best_weight = 0;
    b_best_solution = calloc(n, sizeof(int));
    b_current_solution = calloc(n, sizeof(int));
    b_current_value = 0;
    b_current_weight = 0;
    
    printf("    开始回溯搜索（时间限制: %.0f秒）...\n", time_limit);
    start_time = clock();
    
    // 开始回溯
    int timeout_flag = backtrack(0, n, items, capacity);
    
    if (timeout_flag) {
        result.timeout = 1;
        printf("    搜索因时间限制而终止\n");
    } else {
        printf("    搜索完成（在时间限制内完成所有搜索）\n");
    }
    
    // 复制结果
    result.total_value = b_max_value;
    result.total_weight = b_best_weight;
    memcpy(result.selected, b_best_solution, n * sizeof(int));
    
    // 释放全局变量内存
    free(b_best_solution);
    free(b_current_solution);
    
    return result;
}

// 输出结果到文件
void output_result_to_file(const char* filename, bItem items[], int n, Result result) {
    FILE *file = fopen(filename, "w");
    if (file == NULL) {
        printf("无法创建输出文件 %s\n", filename);
        return;
    }
    
    if (result.timeout) {
        fprintf(file, "注意：算法因时间限制(%.0f秒)而提前终止，结果可能不是最优解\n\n", time_limit);
    }
    
    // 输出选择的物品（需要根据原始编号输出）
    fprintf(file, "选择的物品（编号 重量 价值）:\n");
    for (int i = 0; i < n; i++) {
        if (result.selected[i]) {
            // 找到对应的物品信息（因为items已经被排序了）
            for (int j = 0; j < n; j++) {
                if (items[j].id == i) {
                    fprintf(file, "%d %d %.2f\n", i + 1, items[j].weight, items[j].value);
                    break;
                }
            }
        }
    }
    
    // 输出总重量、总价值和时间开销
    fprintf(file, "总重量: %d\n", result.total_weight);
    fprintf(file, "总价值: %.2f\n", result.total_value);
    fprintf(file, "时间开销: %.6f 秒\n", result.time_cost);
    
    if (result.timeout) {
        fprintf(file, "状态: 因时间限制提前终止\n");
    } else {
        fprintf(file, "状态: 完整搜索完成\n");
    }
    
    fclose(file);
}


int main() {
    printf("=== 回溯法测试器（无物品数量限制版本） ===\n");
    
    
    // 物品数量数组
    int item_counts[] = {1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000, 
                        20000, 40000, 80000, 160000, 320000};
    int num_item_counts = sizeof(item_counts) / sizeof(item_counts[0]);
    
    // 背包容量数组
    int capacities[] = {10000, 100000, 1000000};
    int num_capacities = sizeof(capacities) / sizeof(capacities[0]);
    
    printf("\n开始回溯法测试...\n");
    printf("时间限制: %.0f 秒\n", time_limit);
    printf("注意: 所有规模的数据都会尝试执行，仅受时间限制约束\n\n");
    
    // 对每个物品数量
    for (int i = 0; i < num_item_counts; i++) {
        int item_count = item_counts[i];
        char data_filename[100];
        sprintf(data_filename, "items_%d.txt", item_count);
        
        printf("加载数据文件: %s\n", data_filename);
        
        int n;
        bItem *items = load_test_data(data_filename, &n);
        
        if (items == NULL) {
            printf("跳过文件: %s\n", data_filename);
            continue;
        }
        
        // 对每个背包容量进行测试
        for (int j = 0; j < num_capacities; j++) {
            int capacity = capacities[j];
            
            printf("  测试容量 %d:\n", capacity);
            
            clock_t test_start = clock();
            Result result = backtrack_knapsack(items, n, capacity);
            clock_t test_end = clock();
            
            result.time_cost = ((double)(test_end - test_start)) / CLOCKS_PER_SEC;
            
            // 生成输出文件名
            char output_filename[200];
            sprintf(output_filename, "backtrack_%d_%d.txt", item_count, capacity);
            
            output_result_to_file(output_filename, items, n, result);
            
            if (result.timeout) {
                printf("    完成 (%.6f秒, 价值=%.2f, 提前终止)\n", 
                       result.time_cost, result.total_value);
            } else {
                printf("    完成 (%.6f秒, 价值=%.2f, 完整搜索)\n", 
                       result.time_cost, result.total_value);
            }
            
            if (result.selected != NULL) {
                free(result.selected);
            }
        }
        
        free(items);
        printf("\n");
    }
    
    printf("回溯法测试完成！\n");
    return 0;
}